/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-01-19 11:12:55
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-01-23 10:58:44
 * @FilePath: \LeetCode:\Project\C&C++\leetCode\128.最长连续序列.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=128 lang=cpp
 *
 * [128] 最长连续序列
 * 
 * 方法1：使用并查集分析字串
 * - 问题：使用 hash 的次数过多
 * 
 * 官方题解：
 * 1. 将所有元素加入hash -> 容器构造函数使用
 * 2. 寻找序列开头元素（无 n-1) 确定最长序列
 */

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <iostream>

using namespace std;

// @lc code=start
class Solution
{
public:
    struct node_s
    {
        int parent; // 每个元素的父节点
        int size;   // 每个集合的大小
    };

    unordered_map<int, node_s> hash;

    int len_max = 0;

    node_s find(int x)
    {
        auto it = hash.find(x);
        return (x == it->second.parent) ? it->second : (it->second = find(it->second.parent));
    }

    void unionSet(int x, int y)
    {
        node_s rootX = find(x);
        node_s rootY = find(y);

        if (rootX.parent != rootY.parent) // 合并时将较小的树接到较大的树上
        {
            if (rootX.size < rootY.size)
            {
                hash[rootX.parent].parent = rootY.parent;
                hash[rootY.parent].size += rootX.size;
            }
            else
            {
                hash[rootY.parent].parent = rootX.parent;
                hash[rootX.parent].size += rootY.size;
            }

            if (rootX.size + rootY.size > len_max)
                len_max = rootX.size + rootY.size;
        }
    }

    int longestConsecutive(const vector<int> &nums)
    {
        len_max = nums.size() > 0 ? 1 : 0;

        for (auto n : nums)
        {
            if (hash.find(n) == hash.end())
            {
                hash[n] = {n, 1};
                
                if (hash.find(n + 1) != hash.end())
                    unionSet(n, n + 1);

                if (hash.find(n - 1) != hash.end())
                    unionSet(n, n - 1);
            }
        }

        return len_max;
    }

    int longestConsecutive_00(const vector<int> &nums)
    {
        unordered_set<int> hash(nums.begin(), nums.end());

        int longestSequence = 0;
        for (auto n : hash)
        {
            if (hash.find(n - 1) == hash.end())
            {
                int tail = n + 1; // 当前序列的尾部
                while (hash.find(tail) != hash.end())
                    tail++;
                longestSequence = max(longestSequence, tail - n);
            }
        }

        return longestSequence;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;

    // vector<int> nums = {9, -1, 4, -9, -3, 0, -8, 2, 6, -4, -3, 4, 1, 3, 5, 5, -7, -7, 1, -9, -3, 3, 8, 4, 1, 2};
    vector<int> nums = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
    cout << solution.longestConsecutive(nums) << endl;

    return 0;
}